class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
        if(data.empty())
            return 0;
        int first=GetFirstOfK(data,k,0,data.size()-1);
        int last=GetLastOfK(data,k,0,data.size()-1);
        if(first>-1&&last>-1)
            return last-first+1;
        else
            return 0;
    }
    int GetFirstOfK(const vector<int>& data, const int k, int start, int end ){
        if(start>end)
            return -1;
        int mid=(start+end)>>1;
        if(data[mid]==k){
            if((mid>0&&data[mid-1]!=k)||mid==0)
                return mid;
            else
                end=mid-1;
        }
        else if(data[mid]>k)
            end=mid-1;
        else
            start=mid+1;
        return GetFirstOfK(data,k,start,end);
    }
    int GetLastOfK(const vector<int>& data, const int k, int start, int end ){
        if(start>end)
            return -1;
        int mid=(start+end)>>1;
        if(data[mid]==k){
            if((mid<data.size()-1&&data[mid+1]!=k)||mid==data.size()-1)
                return mid;
            else
                start=mid+1;
        }
        else if(data[mid]>k)
            end=mid-1;
        else
            start=mid+1;
        return GetLastOfK(data,k,start,end);
    }
};